package leetcode;

import java.util.ArrayList;
import java.util.List;

public class Pro22 {
    List<String> resList = new ArrayList<>();

    public static void main(String[] args) {
        Pro22 pro22 = new Pro22();
        System.out.println(pro22.generateParenthesis(3));
    }

    public List<String> generateParenthesis(int n) {
//        List<String> resList = new ArrayList<>();
//        backtracking(0, 0, n, new StringBuilder(), resList);
        backtracking(n, n, "");
        return resList;
    }

    public void backtracking(int left, int right, int n, StringBuilder part, List<String> resList) {
        if (left + right == 2 * n) {
            resList.add(part.toString());
            return;
        }
        if (left < n) {
            part.append("(");
            backtracking(left + 1, right, n, part, resList);
            part.deleteCharAt(part.length() - 1);
        }
        if (right < left) {
            part.append(")");
            backtracking(left, right + 1, n, part, resList);
            part.deleteCharAt(part.length() - 1);
        }
    }

    public void backtracking(int left, int right, String part) {
        if (left == 0 && right == 0) {
            resList.add(part);
            return;
        }
        if (left == right) {
            backtracking(left - 1, right, part + "(");
        } else if (left < right) {
            if (left > 0) {
                backtracking(left - 1, right, part + "(");
            }
            backtracking(left, right - 1, part + ")");
        }
    }
}
